/*
https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/
 */
import java.util.Arrays;

public class Solution338 {
    public int[] countBits(int n) {
        int[] ans=new int[n+1];
        for (int i=1;i<=n;i++){
            ans[i]=ans[i&(i-1)]+1;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution338().countBits(5)));
    }
}
